1. Field of the Invention
The present invention relates to an enciphering and deciphering apparatus and also an enciphering and deciphering method. In particular, the present invention relates to an art of seeking a second expression Yk1 defined by an equation Yk1=Xk1m (where m is a positive integer) based on a first expression Xk1 corresponding to an optional positive integer Xk=Xk1 satisfying an expression shown below in a mathematical system in which modulo n of positive integer is present:Xk=Xk−1+1(1<=k<=n−1, X0=0)
2. Description of a Prior Art
As one of cryptographic techniques, the “RSA” (Rivets, Shimmer, Alderman public key method) cryptographic system is known. In a process for dealing with the RSA ciphers, using a public key (n, e) comprising “n” corresponding to a product of a pair of optional prime numbers “p” and “q” and an optional number “e” satisfying specific restriction against the prime numbers “p” and “q”, in accordance with an equation shown below, a cipher text C is generated by way of enciphering a plain text M:C=Me(mod n)
On the other hand, using a secret key (n, d) comprising a number “d” unilaterally led from the above-referred optional number “e” and prime numbers “p” and “q”, in accordance with an equation shown below, the cipher text C is deciphered before eventually generating a plain text M:M=Cd(mod n)
In this case, if a third party is enabled to secure the prime numbers “p” and “q” by factorizing “n” of the public key (n, e) into prime factors, then, based on the number “e” and the prime numbers “p” and “q”, he or she will be able to become acquainted with the above number “d” very easily before eventually securing the secret key (n, d).
Nevertheless, if the value of the above-referred “n” is enhanced, it will in turn require an enormous time to execute factorization of “n” into prime factors necessary for seeking the prime numbers “p” and “q”, thus making it practically impossible to execute a cryptanalysis. In the RSA cryptographic system, based on the above method by way of enhancing the value of “n”, security of cryptography is ensured.
On the other hand, the above conventional RSA cryptographic system still has problems to solve as cited below. Concretely, when executing a ciphering process, it is required to execute multiplications by e-times per plain text M. Likewise, it is also required to execute multiplications by d-times per cipher text C whenever executing a deciphering process. Accordingly, the greater the value of “n” for ensuring security, the longer the time required for executing an enciphering process and a deciphering process, thus raising problems.
To solve the above problems, it is conceived to use such an enciphering circuit solely consisting of hardware for example. FIG. 21 exemplifies a circuit 1 corresponding to one-bit of a cipher text among an enciphering circuit for converting b-bit of a plain text into b-bit of a cipher text.
The above circuit 1 comprises 2b−1 units of “b-input AND gate 3 and one unit of 2b−1 input OR gate 5. Accordingly, it is required to provide the whole enciphering circuits with a large number of logic gates corresponding to b-times those which are provided for the above circuit 1. Although introduction of the above-referred enciphering circuit will enable contraction of time required for encryption, it will in turn necessitate provision of a huge number of logic gates. The same problem is also present in the deciphering process.
On the other hand, it is also conceived to introduce a method to store all the texts previously enciphered from plain texts. According to this method, unlike the case of executing computations per input of a plain text, time required for encryption can be contracted, and yet, unlike the case of using such an enciphering circuit solely comprising hardware, provision of a huge number of logic gates can be saved. Nevertheless, the greater the value of “n”, the greater the number of memory elements required for provision, and thus, there is a definite limit in the effectiveness of the above conceived method.